package com.shuzijun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses{
    public static void main(String[] args) {
         
         Solution solution = new RestoreIpAddresses().new Solution();
        
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private ArrayList<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        backTrack(s,0,0,new ArrayList<>());
        return result;
    }

        private void backTrack(String s, int k, int step, ArrayList<Object> path) {
            if (k == s.length() && step == 4){
                StringBuilder builder = new StringBuilder();
                for (int i = 0; i < 3; i++) {
                    builder.append(path.get(i)+".");
                }
                builder.append(path.get(3));
                result.add(builder.toString());
                return;
            }

            if (step > 4){
                return;
            }

            if (k == s.length()){
                return;
            }

            int val = 0;
            if (k <s.length()){
                val = val*10 + (s.charAt(k)-'0');
                path.add(val);
                backTrack(s,k+1,step+1,path);
                path.remove(path.size()-1);
            }
            if (s.charAt(k) == '0'){
                return;
            }
            if (k+1 < s.length()){
                val = val*10 + (s.charAt(k+1)-'0');
                path.add(val);
                backTrack(s,k+2,step+1,path);
                path.remove(path.size()-1);
            }

            if (k+2 < s.length()){
                val = val*10 +(s.charAt(k+2)-'0');
                if (val <= 255){
                    path.add(val);
                    backTrack(s,k+3,step+1,path);
                    path.remove(path.size()-1);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}